Digital local area networks are categorized into those which have a synchronous clocking scheme and those which have an asynchronous clocking scheme. In a network with a synchronous clocking scheme, one station is designated a master and generates its own clock, and all other stations derive their clock from the incoming signal, regenerated using, for example, a phase lock loop (PLL). In a network with an asynchronous clocking scheme, also referred to as an independently clocked network, each station generates its own clock signal for its own internal use. The internal clock signal is also the signal used for transmitting data to the next station downstream and is therefore sometimes referred to as the transmit clock Tx. Under an ANSI standard X3T9.5, each individually generated clock signal is specified to have a frequency which differs by no more than .+-.50 ppm from a predetermined nominal frequency. Independently clocked networks are preferred where PLL jitter is a problem, such as in high-speed fiber-distributed data networks. The present invention relates to independently clocked networks.
Typically, in a token ring network, data is passed around the ring in the form of packets or frames. Packets, and the temporal gaps between them, are divided into a plurality of 10-bit bytes, each consisting of two 5-bit symbol codes. Since the invention applies at the bit, nibble (symbol) or byte level of granularity, the term "informational unit" is used herein to refer to any of these three levels. From the discussion hereinafter it will be seen that only slight modifications are needed to implement the invention at intermediate levels of granularity, or at multiple-symbol or multiple-byte levels of granularity, so the term "informational unit" will be understood to apply to any desired level of granularity.
Symbols may be data symbols (high order bit is 0) or control symbols (high order bit is 1). Each packet begins with a starting delimiter, consisting of a "J" control symbol followed by a "K" control symbol, and terminates with an ending delimiter, consisting of a "T" control symbol. Under some circumstances, a packet may terminate with an "H" control symbol. If a packet ends with a data symbol instead of a control symbol, it is considered a "stripped frame" and may be deleted from the network. The interpretation and coding scheme for the various symbols are defined in the ANSI standard. This and other aspects of the ANSI standard are described in the related Receiver Synchronization application, and also in U.S. Pat. No. 4,692,894 ("Overflow/Underflow Detection for Elastic Buffer") and U.S. Pat. No. 4,703,486 ("Communication Data Encoder/Decoder Component System Architecture"). Both of these patents issued to Bemis and are assigned to the assignee of the present application. The related Receiver Synchronization application and both Bemis patents are incorporated by reference in their entirety herein.
It should be noted that the terms "packet" and "frame", as used herein, are intended to include stripped frames, even though the ANSI standard often uses the terms in a manner which excludes stripped frames.
Data packets are typically separated from one another in the data stream by a period of time known as an interpacket gap (IPG), or a preamble. Interpacket gaps are usually filled with idle ("I") symbols, which, according to the standard, consist of five "1" bits each. Aside from helping to maintain the communication status, this choice of code for the idle symbol is preferred since if a 1-bit portion, or a full 5-bit symbol, or even a 10-bit byte of idle symbols is deleted or inserted into the data stream unintentionally, the resulting stream still consists of idle symbols.
According to the standard, no station may transmit a data packet until it has already transmitted at least eight bytes of idle (16 idle symbols). Eight idle bytes is therefore the minimum length for an interpacket gap transmitted from the station which originates it. This gap may shorten during transmission and re-transmission around the ring for reasons explained below, but the standard ensures with a high probability that each station receiving information will see interpacket gaps of no fewer than six bytes each. Symbols other than the idle symbol may appear in an inter-packet gap either due to noise or to such occurrences as realignment of start delimiters on byte or symbol boundaries. All bytes which are within packets (including stripped frames) are sometimes referred to herein as active bytes and all bytes between packets are sometimes referred to herein as inactive bytes.
A problem with independently clocked networks recognized early on is that since the Tx clock of any given node may have a frequency as much as 100 ppm faster or slower than the frequency at which data is being received by that node, it is entirely possible that the receiving station will unintentionally detect a different number of incoming bytes or other informational units than the number originally transmitted. That is, if the receiving station has a slower Tx clock than that of the transmitting station, the receiving station will periodically miss one byte of incoming information; similarly, if the receiving station has a Tx clock which is faster than that of the transmitting station, the receiving station will periodically clock in a single received byte twice. Because of the choice of codes for the idle symbol as explained above, unintentional deletion or addition of idle bits, symbols or bytes is not a severe problem. Severe data integrity problems would result, however, if a bit, symbol or byte was deleted from or inserted into a data packet.
To prevent these occurrences, manufacturers implement a dual-port elastic buffer (EB), which is a FIFO having an input port clocked by a receive clock ("Rx"), derived from the incoming signal, and an output port which is clocked by the station's own internally generated Tx clock. Elastic buffers are described in detail in the related Receiver Synchronization application and in the two Bemis patents.
Upon initialization, incoming informational units are initially stored in the EB until the EB reaches a nominal or centered depth, and then the station in which the EB is located begins reading out the bytes sequentially according to its Tx clock. Thus, if a station's Tx clock is slightly faster than the Tx clock of the immediately upstream neighboring station, the EB will gradually reduce in depth from the nominal position as the receiving station reads bytes of incoming information faster than they are being placed in the EB. Similarly, the contents of an EB in a station having a Tx clock which is slower than the Rx clock will grow from the nominal depth gradually to a greater depth as the incoming information is placed in the EB more quickly than the station reads it.
Then, at an opportune time, such as just after the end of a data packet or just before the beginning of the next data packet, the EB is automatically recentered to the nominal depth. If bytes of information must be added in order to accomplish this, they are added as idle units in the inter-frame gap. If bytes of information must be deleted in order to accomplish this, they are deleted from the inter-frame gap. Even if the EB is designed to permit the addition and deletion of informational units with only a 1-bit granularity, neither of these situations cause data integrity problems because of the choice of codes for the idle symbol. Moreover, the maximum frame size is defined so that given the tolerance of .+-.50 ppm in Tx clock frequencies, the re-centering operation would add or delete no more than one byte of idle at a time.
Previously, since the minimum inter-packet gap length for an originator is specified at eight bytes of idle, and the minimum inter-packet gap length for a receiving station is specified at only six bytes of idle, it was thought that sufficient tolerance had been built in such that it was statistically unlikely for the inter-packet gap length to unintentionally fall below the minimum guaranteed receive length of six bytes of idle. Supporting this view was the assumption that in every network having a random distribution of clock frequencies within the specified tolerance, there would be approximately the same number of net byte adders as there are of net byte deleters. However, statistical studies show that in large networks, though the average inter-packet gap length remains at about eight bytes of idle, the size of any particular inter-packet gap stands a significant chance of falling below the guaranteed minimum of six bytes.
In one proposed algorithmic solution to this problem, known as the "square shoulder" algorithm, a counter is added to the EB for counting the number of idle bytes in each IPG. When an idle byte is to be deleted, instead of deleting it automatically from the next IPG, the apparatus waits until an inter-packet gap arrives which is longer than some threshold number, for example seven bytes. One of the idles in that IPG is then deleted. The available depth of the EB is also increased to accommodate additional bytes building up while waiting for a long enough inter-packet gap. When a byte is to be added, as in previous systems, it is simply added in the next IPG to arrive.
Another proposed algorithm, known as the "smooth-shoulder" algorithm, is similar to the square-shoulder algorithm in that the apparatus postpones deletion of idle bytes until a long enough inter-packet gap arrives. It is different, though, in that more than one byte can be deleted from such an IPG if the IPG is longer than a second threshold value. Different numbers of bytes can be deleted depending on the length of the arriving IPG. Again, adding stations add bytes indiscriminately in the next arriving IPG.
A disadvantage of both of these schemes is that only net deleter stations participate in alleviating the problem. Whether a station is a net adder or net deleter depends on the relationship of its Tx clock frequency to that of its immediately upstream neighbor, not to the network nominal or average clock frequency. Thus, only half the stations in an average network are net deleters, and in any particular network, only a few may be net deleters. In the worst case, only a very small percentage of the stations on the network may participate in alleviating the problem.